perm filename GEOMES.DOC[GEM,BGB]1 blob
sn#030938 filedate 1973-03-25 generic text, type T, neo UTF8
00100 STANFORD ARTIFICIAL INTELLIGENCE LABORATORY MARCH 1973
00200 AIM - XX.
00300
00400 draft - draft - draft - draft - draft - draft - draft - draft - draft
00500
00600 GEOMES - GEOMETRIC MODELING EMBEDDED IN SAIL.
00700
00800
00900 Bruce g. Baumgart
01000
01100
01200 ABSTRACT:
01300
01400 This paper explains the SAIL accessible subroutine package
01500 called GEOMES. Using GEOMES, arbitrary polyhedron models can be
01600 contructed; moved about and viewed in perspective with hidden lines
01700 eliminated. In addition to polyhedra; GEOMES provides models for
01800 cameras and images so that simulators relevant to computer vision,
01900 problem solving, and animation can be constructed.
02000
02100
02200 FIRST EXPLAINATION -
02300 SECOND EXPLAINATION -
02400 THIRD EXPLAINATION -
02500
02600 - DATA STRUCTURE.
02700 - POLYHEDRON OPERATIONS.
02800 - EUCLIDEAN TRANSFORMATIONS.
02900 - IMAGE OPERATIONS.
03000 - EXERCISES.
03100
03200 SUMMARY GEOMES PRIMITIVES.
03300
03310 SHORT EXAMPLES.
03400 EXTENDED EXAMPLES.
03500 1. Tower Planner.
03600 2. Insect Walker.
03700 3. Newton Blocks.
00100 BEGIN "TEST1"
00200 DEFINE !="COMMENT";
00300 DEFINE π="3.1415927";
00400 REQUIRE "⊂⊃⊂⊃" DELIMITERS;
00500 REQUIRE "GEOMES.HDR" SOURCE_FILE;
00600
00700 INTEGER B1,B2,F,E,V,V0,T;
00800 INTEGER WORLD,WINDOW,CAMERA;
00900
01000 ! UNIVERSE CREATION;
01100
01200 WORLD ← MKWORLD; ! MAKE A WORLD;
01300 WINDOW ← MKWINDOW; ! MAKE A WINDOW;
01400 CAMERA ← MKCAMERA; ! MAKE A CAMERA;
01500 BATT(WORLD,WINDOW); ! BODY-ATTACH WORLD TO WINDOW;
01600 BATT(CAMERA,WINDOW); ! BODY-ATTACH CAMERA TO WINDOW;
01700
01800 ! BODY CREATION;
01900
02000 B1 ← MKCUBE(4.0,1.0,2.0); ! MAKE RECTANGULAR PRISM;
02100 B2 ← MKCOPY(B1); ! COPY THE PRISM;
02200
02300 ! ACTION;
02400
02500 FOR T←1 STEP 1 UNTIL 30 DO
02600 OUTSTR(13&10); ! FLUSH THE PAGE PRINTER;
02700 TRANSLATE(B1,0,0,4); ! 4 FEET +Z TOWARDS CAMERA;
02800 ROTATE(B2,π/8,π/8,0); ! ROTATION ABOUT X & Y AXES;
02900 WHILE TRUE DO
03000 BEGIN
03100 ROTATE(B1,0,-π/17,0); ! ROTATION CW ABOUT Y-AXIS;
03200 FOR T←1 STEP 1 UNTIL 40 DO
03300 BEGIN
03400 ROTATE(B1,π/20,0,0); ! ROTATION CCW ABOUT X-AXIS;
03500 ROTATE(B2,0,π/16,0); ! ROTATION CCW ABOUT Y-AXIS;
03600 SHOW2(WINDOW,1); ! DISPLAY A SIMULATED IMAGE;
03700 IF INCHRS≥1 THEN DONE; ! EXIT ON TYPE-ANY-KEY;
03800 END;
03900 END;
04000
04100 END "TEST1"; BGB 19 MARCH 1973.
00100 I. FIRST EXPLAINATION - RUNNING GEOMES.
00200
00300 This first explaination presents a small and restricted
00400 subset of GEOMES for construction and animation using bricks. Please
00500 now read the example program, TEST1. In the example, GEOMES is
00600 declared by requiring the source file GEOMES.HDR[SAI,BGB] under horse
00700 shoe delimiters. When executed, TEST1 displays one cubic brick
00800 tumbling around another.
00900
01000
01100 1st - DATA STRUCTURE:
01200
01300 GEOMES has a representation for the things called "world",
01400 "window", "camera" and "body"; such things are always referred to by
01500 an integer pointer. A world is a set of bodies; a camera is a camera
01600 model; a window ties pairs of cameras and worlds together; and a body
01700 is a model of a polyhedron composed of faces, edges and vertices. The
01800 only kind of body available is a rectangular right prism. To get your
01900 data structure initialized, write the following instructions:
02000
02100 WORLD ← MKWORLD; make world.
02200 WINDOW ← MKWINDOW; make window.
02300 CAMERA ← MKCAMERA; make camera.
02400 BATT(WORLD,WINDOW);
02500 BATT(CAMERA,WINDOW);
02600
02700
02800 1st - POLYHEDRON OPERATIONS:
02900
03000 BODY ← MKCUBE(XSIDE,YSIDE,ZSIDE); make cubic solid.
03100 BODY ← MKCOPY(BODY); make a copy.
03200
03300 The routine MKBODY generates a rectangular right prism with
03400 sides of length XSIDE, YSIDE and ZSIDE. The center of the prism is
03500 initially at the world origin, (0,0,0). The arguments are real
03600 numbers representing feet. The initial camera is located sixteen feet
03700 above the X-Y plane and is looking down with a 12.5 millimeter lens,
03800 which means that any block with sides less than 20 feet will be in
03900 view. The routine MKCOPY will return a copy of its argument, the new
04000 body will have the same location and orientation as the old one, and
04100 should be moved before a hidden line elimination.
04200
04300 WHOLE ← BATT(PART,WHOLE); body attach.
04400 PART ← BDET(PART); body detach.
04500
04600 The BATT routine attachs one body to another so that when
04700 something is moved or copied all its parts will be moved or copied
04800 too. Naturally, parts may have subparts and so on. A body is freed
04900 from its role as a part of something by the BDET routine.
00100 1st - EUCLIDEAN TRANSFORMATIONS:
00200
00300 TRANSLATE(OBJECT,DELTAX,DELTAY,DELTAZ);
00400 ROTATE(OBJECT,ABOUTX,ABOUTY,ABOUTZ);
00500
00600 The TRANSLATE routine takes four arguments, the first
00700 argument is the integer pointing at the thi}g to be translated, the
00800 next three arguments are real numbers indicating a displacement in
00900 feet parallel to the X, Y and Z world axes respectively. The world
01000 frame of reference is right handed and orthogonal.
01100
01200 The ROTATE routine takes four arguments, the first argument
01300 is the integer pointing at the thing to be rotated, and the next
01400 three arguments are real numbers indicating a angular displacement in
01500 radians about the X, Y and Z world axes respectively. The positive
01600 direction of rotation is counterclockwise; which is the so called
01700 right hand rule convention.
01800
01900
02000 1st - IMAGE OPERATIONS:
02100
02200 INTEGER PROCEDURE SHOW1 (INTEGER WINDOW,GLASS);
02300 INTEGER PROCEDURE SHOW2 (INTEGER WINDOW,GLASS);
02400
02500 There are two simple display operations: SHOW1 and SHOW2.
02600 The SHOW1 routine displays all the edges appearing in the window. The
02700 SHOW2 routine performs a hidden line elimination and displays only
02800 the portions of edges that are not occultated. Both routines take two
02900 arguments, the first argument is the window to be displayed and the
03000 second argument is the number, 0 to 15, of the III piece of glass to
03100 which the display buffer is sent.
03200
03300
03400 1st - EXERCISES:
03500
03600 1. Make the tower shown in the figure using 1,2,4 bricks.
03700 2. Make a table with four chairs. (use the BATT and MKCOPY).
03800 3. Make a simulation of a small bouncing cube.
00100 SECOND EXPLAINATION.
00200
00300 2nd - DATA STRUCTURE.
00400
00500 The GEOMES data structure is implemented as twelve word
00600 blocks containing pointers and data in the fashion usual to graphics
00700 and simulation; an introduction to this technology can be found in
00800 Knuth. The language of implementation is PDP-10 machine code, and
00900 although the data and subroutines discussed below are accessible from
01000 SAIL, with the exception of CORGET, no SAIL routines are called by
01100 GEOMES routines. In particular, GEOMES emphatically has nothing to do
01200 with LEAP.
01300
01400 The twelve word blocks of GEOMES are called "nodes". Nodes
01500 are referred to by their actual machine address in the user core
01600 image, which is an integer called a "link". Thus the subroutines that
01700 take nodes as arguments or return nodes as values pass links rather
01800 than the nodes themselves. In SAIL, the user core image can be
01900 accessed as a special array named MEMORY. Using the MEMORY feature of
02000 SAIL, the GEOMES.HDR defines names for where links and data are
02100 stored relative to the origin of a node.
02200
00100 2nd - POLYHEDRON OPERATIONS.
00100 2nd - EUCLIDEAN TRANSFORMATIONS.
00100 2nd - IMAGE OPERATIONS.
00100 NODE ← MKNODE(INTEGER TYP);
00200 NIL ← KLNODE(INTEGER NODE);
00300
00400 WORLD ← MKWORLD;
00500 WINDOW ← MKWINDOW;
00600 CAMERA ← MKCAMERA;
00700 LO ← MKLOCOR;
00800
00900 B ← MKB(WORLD);
01000 NIL ← KLB(WORLD);
01100 NIL ← KLBFEV(WORLD);
01200
01300 F ← MKF(B);
01400 E ← MKE(B);
01500 V ← MKV(B);
01600
01700 NIL ← WING(E1,E2);
01800 BOOL ← LINKED(Q1,Q2);
01900
02000 E ← ECW(FEV,FEV);
02100 E ← ECCW(FEV,FEV);
02200 FV ← OTHER(E,FV);